package com.leo.datastruct.tree;

/**
 *
 * @author xuexiaolei
 * @version 2018年02月04日
 */
public class AVLTree<T extends Comparable<T>> {
    private AVLNode<T> mRoot;

    class AVLNode<T extends Comparable<T>>{
        T key;
        int height = 0;
        AVLNode<T> left = null;
        AVLNode<T> right = null;

        public AVLNode() {}

        public AVLNode(T key) {
            this.key = key;
        }

        public AVLNode(T key, int height) {
            this.key = key;
            this.height = height;
        }

        public AVLNode(T key, int height, AVLNode<T> left, AVLNode<T> right) {
            this.key = key;
            this.height = height;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 获取树的高度
     * @param node
     * @return
     */
    private int getHeight(AVLNode<T> node){
        if (node!= null){
            return node.height;
        }
        return 0;
    }

    //******************************旋转 start************************************************

    /**
     * 左左旋转，实际上是对节点进行了一次右旋
     * @param k2
     * @return      返回旋转后的根节点
     */
    private AVLNode<T> leftLeftRotation(AVLNode<T> k2){
        AVLNode<T> k1= k2.left;
        k2.left = k1.right;
        k1.right = k2;

        k2.height = Math.max(getHeight(k2.left), getHeight(k2.right)) + 1;
        k1.height = Math.max(getHeight(k1.left), getHeight(k1.right)) + 1;
        return k1;
    }

    /**
     * 右右旋转
     * @param k1
     * @return
     */
    private AVLNode<T> rightRightRotation(AVLNode<T> k1){
        AVLNode<T> k2 = k1.right;
        k1.right = k2.left;
        k2.left = k1;

        k1.height = Math.max(getHeight(k1.left), getHeight(k1.right)) + 1;
        k2.height = Math.max(getHeight(k2.left), getHeight(k2.right)) + 1;
        return k2;
    }

    /**
     * 左右
     * @param k3
     * @return
     */
    private AVLNode<T> leftRightRotation(AVLNode<T> k3){
        k3.left = rightRightRotation(k3.left);
        return leftLeftRotation(k3);
    }

    /**
     * 右左
     * @param k3
     * @return
     */
    private AVLNode<T> rightLeftRotation(AVLNode<T> k3){
        k3.right = leftLeftRotation(k3.right);
        return rightRightRotation(k3);
    }

    //******************************旋转 end************************************************
    //******************************查找 start************************************************
    /**
     * (递归实现)查找"AVL树x"中键值为key的节点
     */
    private AVLNode<T> search(AVLNode<T> x, T key) {
        if (x==null) {return null;}

        int cmp = key.compareTo(x.key);
        if (cmp < 0) {
            return search(x.left, key);
        }else if (cmp > 0) {
            return search(x.right, key);
        }else {
            return x;
        }
    }

    public AVLNode<T> search(T key) {
        return search(mRoot, key);
    }
    //******************************查找 end************************************************



    //******************************插入 start************************************************

    /**
     * key插入到树中，并返回插入后的根节点    递归写法
     * @param tree  AVL树的根结点
     * @param key   插入的结点的键值
     * @return      根节点
     */
    public AVLNode<T> insert(AVLNode<T> tree, T key){
        if (tree == null){
            tree = new AVLNode<>(key);
        }else {
            int cmp = key.compareTo(tree.key);
            if (cmp < 0){
                tree.left = insert(tree.left, key);
                if (getHeight(tree.left) - getHeight(tree.right) == 2){
                    if (key.compareTo(tree.left.key) < 0){
                        tree = leftLeftRotation(tree);
                    }else {
                        tree = leftRightRotation(tree);
                    }
                }
            }else if (cmp > 0){
                tree.right =  insert(tree.right, key);
                if (getHeight(tree.right) - getHeight(tree.left) == 2){
                    if (key.compareTo(tree.right.key) > 0){
                        tree = rightRightRotation(tree);
                    }else {
                        tree = rightLeftRotation(tree);
                    }
                }
            }else{
                throw new RuntimeException("不允许插入相同的节点");
            }
        }
        tree.height = Math.max(getHeight(tree.left), getHeight(tree.right)) + 1;
        return tree;
    }

    public void insert(T key){
        mRoot = insert(mRoot, key);
    }


    //******************************插入 end************************************************

    //******************************删除 start************************************************

    /**
     * 删除tree树中的dNode节点，并返回根节点
     * @param tree
     * @param dNode
     * @return
     */
    private AVLNode<T> remove(AVLNode<T> tree, AVLNode<T> dNode){
        if (tree==null){ return null; }
        int cmp = dNode.key.compareTo(tree.key);
        if (cmp < 0){
            tree.left = remove(tree.left, dNode);
            if (getHeight(tree.right) - getHeight(tree.left) == 2){
                if (getHeight(tree.right.left) > getHeight(tree.right.right)){
                    tree = rightLeftRotation(tree);
                }else {
                    tree = rightRightRotation(tree);
                }
            }
        }else if (cmp > 0){
            tree.right = remove(tree.right, dNode);
            if (getHeight(tree.left) - getHeight(tree.right) == 2){
                if (getHeight(tree.left.left) > getHeight(tree.left.right)){
                    tree = leftLeftRotation(tree);
                }else {
                    tree = leftRightRotation(tree);
                }
            }
        }else {// tree是对应要删除的节点
            // tree的左右孩子都非空
            if ((tree.left!=null) && (tree.right!=null)) {
                if (getHeight(tree.left) > getHeight(tree.right)) {
                    // 如果tree的左子树比右子树高；
                    // 则(01)找出tree的左子树中的最大节点
                    //   (02)将该最大节点的值赋值给tree。
                    //   (03)删除该最大节点。
                    // 这类似于用"tree的左子树中最大节点"做"tree"的替身；
                    // 采用这种方式的好处是：删除"tree的左子树中最大节点"之后，AVL树仍然是平衡的。
                    AVLNode<T> max = maximum(tree.left);
                    tree.key = max.key;
                    tree.left = remove(tree.left, max);
                } else {
                    // 如果tree的左子树不比右子树高(即它们相等，或右子树比左子树高1)
                    // 则(01)找出tree的右子树中的最小节点
                    //   (02)将该最小节点的值赋值给tree。
                    //   (03)删除该最小节点。
                    // 这类似于用"tree的右子树中最小节点"做"tree"的替身；
                    // 采用这种方式的好处是：删除"tree的右子树中最小节点"之后，AVL树仍然是平衡的。
                    AVLNode<T> min = minimum(tree.right);
                    tree.key = min.key;
                    tree.right = remove(tree.right, min);
                }
            }else {
                AVLNode<T> tmp = tree;
                tree = (tree.left!=null) ? tree.left : tree.right;
                tmp = null;
            }
        }
        if(tree != null){ tree.height = Math.max(getHeight(tree.left), getHeight(tree.right)) + 1;}
        return tree;
    }

    public void remove(T key){
        AVLNode<T> search= search(key);
        if (search != null){
            mRoot = remove(mRoot, search);
        }
    }

    //******************************删除 end************************************************

    //******************************最值 start************************************************
    /**
     * 查找最小结点：返回tree为根结点的AVL树的最小结点。
     */
    private AVLNode<T> minimum(AVLNode<T> tree) {
        if (tree == null) {return null;}
        while(tree.left != null){ tree = tree.left;}
        return tree;
    }
    public T minimum() {
        AVLNode<T> p = minimum(mRoot);
        if (p != null) {return p.key;}
        return null;
    }

    /**
     * 查找最大结点：返回tree为根结点的AVL树的最大结点。
     */
    private AVLNode<T> maximum(AVLNode<T> tree) {
        if (tree == null) {return null;}
        while(tree.right != null) {tree = tree.right;}
        return tree;
    }
    public T maximum() {
        AVLNode<T> p = maximum(mRoot);
        if (p != null) {return p.key;}
        return null;
    }
    //******************************最值 end************************************************

}
